class Solution
{
public:
    long long beautifulSubstrings(string s, int k)
    {
        int n = s.size();
        unordered_map<int, vector<long long>> groups;
        int volwelCount = 0;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' ||
                s[i] == 'u')
            {
                ++volwelCount;
            }
            int diff = i + 1 - 2 * volwelCount;
            groups[diff].push_back(i);
        }
        int minDiffLen = 1;
        while (minDiffLen * minDiffLen % k != 0)
        {
            ++minDiffLen;
        }
        minDiffLen *= 2;
        long long ans = 0;
        for (auto &[diff, indices] : groups)
        {
            int m = indices.size();
            unordered_map<int, int> diffLenCount;
            if (diff == 0)
            {
                diffLenCount[0] = 1;
            }
            for (int i = 0; i < m; ++i)
            {
                int len = indices[i] + 1;
                len %= minDiffLen;
                ans += diffLenCount[len];
                ++diffLenCount[len];
            }
        }
        return ans;
    }
};